#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        vector<int> ret;
        int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
        while (left <= right && up <= down)
        {
            for (int j = left; j <= right; j++) ret.push_back(matrix[up][j]);
            if (++up > down) break;
            for (int i = up; i <= down; i++) ret.push_back(matrix[i][right]);
            if (--right < left) break;
            for (int j = right; j >= left; j--) ret.push_back(matrix[down][j]);
            if (--down < up) break;
            for (int i = down; i >= up; i--) ret.push_back(matrix[i][left]);
            if (++left > right) break;
        }
        return ret;
    }
};
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m);
        vector<bool> col(n);

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0) row[i] = col[j] = true;
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }

    }
};
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
        }
        for (int i = 0; i < n; i++)
        {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = 1, g[n - 1] = 1;
        vector<int> ret(n);
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--) g[i] = g[i + 1] * nums[i + 1];

        for (int i = 0; i < n; i++) ret[i] = f[i] * g[i];

        return ret;
    }
};
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head)
    {
        Node* newhead = nullptr, * newtail = nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> hash;
        while (cur)
        {
            Node* newnode = new Node(cur->val);
            if (newhead == nullptr)
            {
                newhead = newtail = newnode;
            }
            else
            {
                newtail->next = newnode;
                newtail = newtail->next;
            }
            hash[cur] = newnode;
            cur = cur->next;
        }

        cur = head;
        while (cur)
        {
            hash[cur]->random = hash[cur->random];
            cur = cur->next;
        }
        return newhead;
    }
};
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root)
    {
        if (!root) return 0;
        queue<Node*> q;
        q.push(root);
        int ret = 0;
        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                Node* front = q.front(); q.pop();
                for (auto e : front->children) q.push(e);
            }
            ret++;
        }
        return ret;
    }
};
